package 代码随想录_动态规划.背包_01;

/**
 * @author zx
 * @create 2022-05-24 16:20
 * 只有确定了如下四点，才能把01背包问题套到本题上来。
 *      背包的体积为sum / 2
 *      背包要放入的商品(集合里的元素)重量为元素的数值,价值也为元素的数值
 *      背包如何正好装满,说明找到了总和为 sum / 2 的子集。
 *      背包中每一个元素是不可重复放入。
 *
 * 1.确定dp数组（dp table）以及下标的含义
 *  dp[i]表示 背包总容量是i，最大可以凑成i的子集总和为dp[i]。
 * 2.确定递推公式
 *  dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
 * 3.dp数组如何初始化
 *  非0下标都初始化为0
 * 4.确定遍历顺序
 *
 * 5.举例推导dp数组
 *
 *
 * 本题与 0-1 背包问题有一个很大的不同，即：
 * 0-1 背包问题选取的物品的容积总量 不能超过 规定的总量；
 * 本题选取的数字之和需要 恰好等于 规定的和的一半。
 * 组成部分四：计算顺序
 */
public class 分割等和子集_416 {
    /**
     * @return (题型二)：相当于是求背包是否正好装满
     *
     * 对比背包问题二：发现一维优化中dp[i]的含义由题目要求决定
     */
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for(int i = 0;i < nums.length;i++){
            sum += nums[i];
        }
        //本题选取的数字之和需要恰好等于规定的和的一半,即sum必须是偶数
        if(sum % 2 == 1){
            return false;
        }
        int target = sum / 2;
        int[] dp = new int[target + 1];
        //物品：num[i],背包容量：sum / 2;
        for(int i = 0;i < nums.length;i++){//遍历物品
            for(int j = target;j >= nums[i];j--){//遍历背包容量
                dp[j] = Math.max(dp[j],dp[j - nums[i]] + nums[i]);
            }
        }
        //如果dp[i] == i 说明集合中的子集总和正好可以凑成总和i,理解这一点很重要
        if (dp[target] == target) {
            return true;
        }
        return false;
    }
}
